/**
Date:20220321 21:59PM
key:1.序列化就是普通的层序遍历，空的节点用特殊字符表示。
    2.反序列化时节点的左右坐标分别是 2*(i-totalNumberOfNull[i])+1,2*(i-totalNumberOfNull[i])+2 。

 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string res="";
        if(root==NULL){return res;}
        queue<TreeNode*>q;
        q.push(root);
        //res+=to_string(root->val);
        while(!q.empty())
        {
            if(q.front()!=NULL)
            {
                q.push(q.front()->left);
                q.push(q.front()->right);
                
                res+=to_string(q.front()->val);
            }
            else
            {
                res+="n";
            }
            res+="/";
            q.pop();
        }
        //cout<<res;
        return res;
    }
    TreeNode* creat(vector<int>&data,int i,vector<int>&numberOfN) {

        if((i>=data.size())||(data[i]==INT_MIN)){return NULL;}
        TreeNode*root=new TreeNode(data[i]);
        //cout<<data[i]<<" ";
        root->left=creat(data,2*(i-numberOfN[i])+1,numberOfN);
        root->right=creat(data,2*(i-numberOfN[i])+2,numberOfN);
        return root;
    }
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data.size()==0){return NULL;}
        TreeNode* root=NULL;
        vector<int>v;
        string tmp="";
        for(int i=0;i<data.size();i++)
        {
            if(data[i]=='/')
            {
                if(tmp=="n")
                {
                    v.push_back(INT_MIN);
                }else{
                    v.push_back(stoi(tmp));
                }
                
                tmp="";
            }
            else
            {
                tmp+=data[i];
            }
        }
        //for(int t:v){cout<<t<<" ";}
        vector<int>numberOfN(v.begin(),v.end());
        numberOfN[0]=0;
        
        for(int ii=1;ii<numberOfN.size();ii++)
        {
            
            if(numberOfN[ii]==INT_MIN)
            {
                numberOfN[ii]=numberOfN[ii-1]+1;
            }else{
                numberOfN[ii]=numberOfN[ii-1];
            }
        }
        
        return creat(v,0,numberOfN);
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));